package Acwing.搜索与图论;

import java.util.Scanner;

/**
 * @Title: nQueenQuestion
 * @Author 贾金博
 * @Package Acwing.搜索与图论
 * @Date 2025/4/11 下午6:20
 * @description: n皇后问题
 */
public class nQueenQuestion{

    private static int n;
    private static char[][] c;
    private static boolean[] h;
    private static boolean[] l;
    private static boolean[] djx1; // 对角线1
    private static boolean[] djx2; // 对角线2

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        c = new char[n + 10][n + 10];
        h = new boolean[n + 10];
        l = new boolean[n + 10];
        djx1 = new boolean[n + 100];
        djx2 = new boolean[n + 100];

        // 对 数组 c 进行初始化
        for(int i = 1; i <= n; i ++ ) {
            for(int j = 1; j <= n; j ++ ) {
                c[i][j] = '.';
            }
        }
        dfs(1);
    }

    // n 皇后问题
    private static void dfs(int len) {
        if(len == n + 1) {
            for(int i = 1; i <= n; i ++ ) {
                for(int j = 1; j <= n; j ++ ) {
                    System.out.print(c[i][j]);
                }
                System.out.println();
            }
            System.out.println();
            return ;
        }

        // 看看当前这一行可以去放到哪一列
        for(int i = 1; i <= n; i ++ ) {
            if(!h[len] && !l[i] && !djx1[len - i + 100] && !djx2[i + len]) {
                c[len][i] = 'Q';
                h[len] = true;
                l[i] = true;
                djx1[len - i + 100] = true;
                djx2[i + len] = true;

                dfs(len + 1);

                c[len][i] = '.';
                h[len] = false;
                l[i] = false;
                djx1[len - i + 100] = false;
                djx2[i + len] = false;
            }
        }
    }
}
